// Deflater.HuffmanTree.cs
//
// Copyright (C) 2001 Mike Krueger
// Copyright (C) 2004 John Reilly
// Copyright (C) 2010 Thomas Maierhofer
//
// (2010) This Code was modified from SharpZipLib http://www.icsharpcode.net/OpenSource/SharpZipLib/  
// to fit the needs of Second WAF - a heavy load web application framework 
//
// This file was translated from java, it was part of the GNU Classpath
// Copyright (C) 2001 Free Software Foundation, Inc.
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//
// Linking this library statically or dynamically with other modules is
// making a combined work based on this library.  Thus, the terms and
// conditions of the GNU General Public License cover the whole
// combination.
// 
// As a special exception, the copyright holders of this library give you
// permission to link this library with independent modules to produce an
// executable, regardless of the license terms of these independent
// modules, and to copy and distribute the resulting executable under
// terms of your choice, provided that you also meet, for each linked
// independent module, the terms and conditions of the license of that
// module.  An independent module is a module which is not derived from
// or based on this library.  If you modify this library, you may extend
// this exception to your version of the library, but you are not
// obligated to do so.  If you do not wish to do so, delete this
// exception statement from your version.

namespace WAF.Content
{
    using System;
    public partial class Deflater
    {

        internal class HuffmanTree
        {
            internal struct Symbol
            {
                internal ushort Bits;       // How many bits of code are valid
                internal ushort BitsCode;   // The Value of the Bits
            }


            public short[] frequencies;

            internal Symbol[] symbols;

            public int minNumCodes;
            public uint numCodes;



            int[] bl_counts;
            int maxLength;
            Deflater deflater;


            public HuffmanTree(Deflater deflater, int elems, int minCodes, int maxLength)
            {
                this.deflater = deflater;
                this.minNumCodes = minCodes;
                this.maxLength = maxLength;
                frequencies = new short[elems];
                bl_counts = new int[maxLength];
            }


            /// <summary>
            /// Resets the internal state of the tree
            /// </summary>
            public void Reset()
            {
                for (int i = 0; i < frequencies.Length; i++)
                {
                    frequencies[i] = 0;
                }
                // codes = null;
                symbols = null;
            }

            public void WriteSymbol(int code)
            {
                deflater.OutputBufferWriteSymbol(symbols[code]);
            }

            /// <summary>
            /// Check that all frequencies are zero
            /// </summary>
            /// <exception cref="SharpZipBaseException">
            /// At least one frequency is non-zero
            /// </exception>
            public void CheckEmpty()
            {
                bool empty = true;
                for (int i = 0; i < frequencies.Length; i++)
                {
                    if (frequencies[i] != 0)
                    {
                        //Console.WriteLine("freqs[" + i + "] == " + freqs[i]);
                        empty = false;
                    }
                }

                if (!empty)
                {
                    throw new InvalidOperationException("!Empty");
                }
            }

            /// <summary>
            /// Set static codes and length
            /// </summary>
            /// <param name="staticCodes">new codes</param>
            /// <param name="staticLengths">length for new codes</param>
            public void SetStaticCodes(Symbol[] symbols)
            {
                this.symbols = symbols;
            }

            /// <summary>
            /// Build dynamic codes and lengths
            /// </summary>
            public void BuildCodes()
            {
                int numSymbols = frequencies.Length;
                uint[] nextCode = new uint[maxLength];
                uint code = 0;

                // codes = new ushort[frequencies.Length];

                //				if (DeflaterConstants.DEBUGGING) {
                //					//Console.WriteLine("buildCodes: "+freqs.Length);
                //				}

                for (int bits = 0; bits < maxLength; bits++)
                {
                    nextCode[bits] = code;
                    code += (uint)(bl_counts[bits] << (15 - bits));

                    //					if (DeflaterConstants.DEBUGGING) {
                    //						//Console.WriteLine("bits: " + ( bits + 1) + " count: " + bl_counts[bits]
                    //						                  +" nextCode: "+code);
                    //					}
                }


                for (int i = 0; i < numCodes; i++)
                {
                    int bits = symbols[i].Bits;
                    if (bits > 0)
                    {

                        //						if (DeflaterConstants.DEBUGGING) {
                        //								//Console.WriteLine("codes["+i+"] = rev(" + nextCode[bits-1]+"),
                        //								                  +bits);
                        //						}

                        symbols[i].BitsCode = BitReverse(nextCode[bits - 1]);
                        nextCode[bits - 1] += (uint)(1 << (16 - bits));
                    }
                }
            }

            public void BuildTree()
            {
                int numSymbols = frequencies.Length;

                /* heap is a priority queue, sorted by frequency, least frequent
                * nodes first.  The heap is a binary tree, with the property, that
                * the parent node is smaller than both child nodes.  This assures
                * that the smallest node is the first parent.
                *
                * The binary tree is encoded in an array:  0 is root node and
                * the nodes 2*n+1, 2*n+2 are the child nodes of node n.
                */
                int[] heap = new int[numSymbols];
                int heapLen = 0;
                int maxCode = 0;
                for (int n = 0; n < numSymbols; n++)
                {
                    int freq = frequencies[n];
                    if (freq != 0)
                    {
                        // Insert n into heap
                        int pos = heapLen++;
                        int ppos;
                        while (pos > 0 && frequencies[heap[ppos = (pos - 1) / 2]] > freq)
                        {
                            heap[pos] = heap[ppos];
                            pos = ppos;
                        }
                        heap[pos] = n;

                        maxCode = n;
                    }
                }

                /* We could encode a single literal with 0 bits but then we
                * don't see the literals.  Therefore we force at least two
                * literals to avoid this case.  We don't care about order in
                * this case, both literals get a 1 bit code.
                */
                while (heapLen < 2)
                {
                    int node = maxCode < 2 ? ++maxCode : 0;
                    heap[heapLen++] = node;
                }

                numCodes = (uint)Math.Max(maxCode + 1, minNumCodes);

                int numLeafs = heapLen;
                int[] childs = new int[4 * heapLen - 2];
                int[] values = new int[2 * heapLen - 1];
                int numNodes = numLeafs;
                for (int i = 0; i < heapLen; i++)
                {
                    int node = heap[i];
                    childs[2 * i] = node;
                    childs[2 * i + 1] = -1;
                    values[i] = frequencies[node] << 8;
                    heap[i] = i;
                }

                /* Construct the Huffman tree by repeatedly combining the least two
                * frequent nodes.
                */
                do
                {
                    int first = heap[0];
                    int last = heap[--heapLen];

                    // Propagate the hole to the leafs of the heap
                    int ppos = 0;
                    int path = 1;

                    while (path < heapLen)
                    {
                        if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]])
                        {
                            path++;
                        }

                        heap[ppos] = heap[path];
                        ppos = path;
                        path = path * 2 + 1;
                    }

                    /* Now propagate the last element down along path.  Normally
                    * it shouldn't go too deep.
                    */
                    int lastVal = values[last];
                    while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal)
                    {
                        heap[path] = heap[ppos];
                    }
                    heap[path] = last;


                    int second = heap[0];

                    // Create a new node father of first and second
                    last = numNodes++;
                    childs[2 * last] = first;
                    childs[2 * last + 1] = second;
                    int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
                    values[last] = lastVal = values[first] + values[second] - mindepth + 1;

                    // Again, propagate the hole to the leafs
                    ppos = 0;
                    path = 1;

                    while (path < heapLen)
                    {
                        if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]])
                        {
                            path++;
                        }

                        heap[ppos] = heap[path];
                        ppos = path;
                        path = ppos * 2 + 1;
                    }

                    // Now propagate the new element down along path
                    while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal)
                    {
                        heap[path] = heap[ppos];
                    }
                    heap[path] = last;
                } while (heapLen > 1);

                if (heap[0] != childs.Length / 2 - 1)
                {
                    throw new InvalidOperationException("Heap invariant violated");
                }

                BuildLength(childs);
            }

            /// <summary>
            /// Get encoded length
            /// </summary>
            /// <returns>Encoded length, the sum of frequencies * lengths</returns>
            public int GetEncodedLength()
            {
                int len = 0;
                for (int i = 0; i < frequencies.Length; i++)
                {
                    len += frequencies[i] * symbols[i].Bits;
                }
                return len;
            }

            /// <summary>
            /// Scan a literal or distance tree to determine the frequencies of the codes
            /// in the bit length tree.
            /// </summary>
            public void CalcBLFreq(HuffmanTree blTree)
            {
                int max_count;               /* max repeat count */
                int min_count;               /* min repeat count */
                int count;                   /* repeat count of the current code */
                int curlen = -1;             /* length of current code */

                int i = 0;
                while (i < numCodes)
                {
                    count = 1;
                    int nextlen = symbols[i].Bits;
                    if (nextlen == 0)
                    {
                        max_count = 138;
                        min_count = 3;
                    }
                    else
                    {
                        max_count = 6;
                        min_count = 3;
                        if (curlen != nextlen)
                        {
                            blTree.frequencies[nextlen]++;
                            count = 0;
                        }
                    }
                    curlen = nextlen;
                    i++;

                    while (i < numCodes && curlen == symbols[i].Bits)
                    {
                        i++;
                        if (++count >= max_count)
                        {
                            break;
                        }
                    }

                    if (count < min_count)
                    {
                        blTree.frequencies[curlen] += (short)count;
                    }
                    else if (curlen != 0)
                    {
                        blTree.frequencies[REP_3_6]++;
                    }
                    else if (count <= 10)
                    {
                        blTree.frequencies[REP_3_10]++;
                    }
                    else
                    {
                        blTree.frequencies[REP_11_138]++;
                    }
                }
            }

            /// <summary>
            /// Write tree values
            /// </summary>
            /// <param name="blTree">Tree to write</param>
            public void WriteTree(HuffmanTree blTree)
            {
                int max_count;               // max repeat count
                int min_count;               // min repeat count
                uint count;                   // repeat count of the current code
                int curlen = -1;             // length of current code

                int i = 0;
                while (i < numCodes)
                {
                    count = 1;
                    int nextlen = symbols[i].Bits;
                    if (nextlen == 0)
                    {
                        max_count = 138;
                        min_count = 3;
                    }
                    else
                    {
                        max_count = 6;
                        min_count = 3;
                        if (curlen != nextlen)
                        {
                            blTree.WriteSymbol(nextlen);
                            count = 0;
                        }
                    }
                    curlen = nextlen;
                    i++;

                    while (i < numCodes && curlen == symbols[i].Bits)
                    {
                        i++;
                        if (++count >= max_count)
                        {
                            break;
                        }
                    }

                    if (count < min_count)
                    {
                        while (count-- > 0)
                        {
                            blTree.WriteSymbol(curlen);
                        }
                    }
                    else if (curlen != 0)
                    {
                        blTree.WriteSymbol(REP_3_6);
                        deflater.OutputBufferWriteBits(count - 3, 2);
                    }
                    else if (count <= 10)
                    {
                        blTree.WriteSymbol(REP_3_10);
                        deflater.OutputBufferWriteBits(count - 3, 3);
                    }
                    else
                    {
                        blTree.WriteSymbol(REP_11_138);
                        deflater.OutputBufferWriteBits(count - 11, 7);
                    }
                }
            }

            void BuildLength(int[] childs)
            {
                this.symbols = new Symbol[frequencies.Length];
                int numNodes = childs.Length / 2;
                int numLeafs = (numNodes + 1) / 2;
                int overflow = 0;

                for (int i = 0; i < maxLength; i++)
                {
                    bl_counts[i] = 0;
                }

                // First calculate optimal bit lengths
                int[] lengths = new int[numNodes];
                lengths[numNodes - 1] = 0;

                for (int i = numNodes - 1; i >= 0; i--)
                {
                    if (childs[2 * i + 1] != -1)
                    {
                        int bitLength = lengths[i] + 1;
                        if (bitLength > maxLength)
                        {
                            bitLength = maxLength;
                            overflow++;
                        }
                        lengths[childs[2 * i]] = lengths[childs[2 * i + 1]] = bitLength;
                    }
                    else
                    {
                        // A leaf node
                        int bitLength = lengths[i];
                        bl_counts[bitLength - 1]++;
                        this.symbols[childs[2 * i]].Bits = (byte)lengths[i];
                    }
                }

                //				if (DeflaterConstants.DEBUGGING) {
                //					//Console.WriteLine("Tree "+freqs.Length+" lengths:");
                //					for (int i=0; i < numLeafs; i++) {
                //						//Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
                //						                  + " len: "+length[childs[2*i]]);
                //					}
                //				}

                if (overflow == 0)
                {
                    return;
                }

                int incrBitLen = maxLength - 1;
                do
                {
                    // Find the first bit length which could increase:
                    while (bl_counts[--incrBitLen] == 0)
                        ;

                    // Move this node one down and remove a corresponding
                    // number of overflow nodes.
                    do
                    {
                        bl_counts[incrBitLen]--;
                        bl_counts[++incrBitLen]++;
                        overflow -= 1 << (maxLength - 1 - incrBitLen);
                    } while (overflow > 0 && incrBitLen < maxLength - 1);
                } while (overflow > 0);

                /* We may have overshot above.  Move some nodes from maxLength to
                * maxLength-1 in that case.
                */
                bl_counts[maxLength - 1] += overflow;
                bl_counts[maxLength - 2] -= overflow;

                /* Now recompute all bit lengths, scanning in increasing
                * frequency.  It is simpler to reconstruct all lengths instead of
                * fixing only the wrong ones. This idea is taken from 'ar'
                * written by Haruhiko Okumura.
                *
                * The nodes were inserted with decreasing frequency into the childs
                * array.
                */
                int nodePtr = 2 * numLeafs;
                for (int bits = maxLength; bits != 0; bits--)
                {
                    int n = bl_counts[bits - 1];
                    while (n > 0)
                    {
                        int childPtr = 2 * childs[nodePtr++];
                        if (childs[childPtr + 1] == -1)
                        {
                            // We found another leaf
                            symbols[childs[childPtr]].Bits = (byte)bits;
                            n--;
                        }
                    }
                }
                //				if (DeflaterConstants.DEBUGGING) {
                //					//Console.WriteLine("*** After overflow elimination. ***");
                //					for (int i=0; i < numLeafs; i++) {
                //						//Console.WriteLine("Node "+childs[2*i]+" freq: "+freqs[childs[2*i]]
                //						                  + " len: "+length[childs[2*i]]);
                //					}
                //				}
            }

        }
    }
}
